#include <iostream>
#include <vector>
using namespace std;

void ShellSort1 (vector<int>& v) {
	int len = v.size();
	for(int gap = len/2 ; gap > 0; gap/=2) {
		for(int group_start_index = 0; group_start_index < gap; group_start_index++) {
			for(int current_index = group_start_index + gap; current_index < len; current_index +=gap) {
				int current_number = v[current_index];
				int pre_index = current_index - gap;
				while(pre_index >= group_start_index && current_number < v[pre_index])
				{
					v[pre_index + gap] = v[pre_index];
					pre_index -= gap;
				}
				v[pre_index + gap] = current_number;
			}
		}
	}
}

void ShellSort2 (vector<int>& v) {
	int len = v.size();
	for(int gap = len/2; gap > 0; gap /= 2) {//排序的轮数
		for(int i = gap; i < len; i++) {
			int cur_num = v[i];
			int pre_index = i - gap;
			while(pre_index >= 0 && cur_num < v [pre_index]) {
				v[pre_index + gap] = v[pre_index];
				pre_index -= gap;
			}
			v[pre_index + gap] = cur_num;
		}
	}	
}

//增量序列的选择？

int main() {
	vector<int> v{1,4,3,2,7,9,5,0,4,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	
	//ShellSort1(v);
	ShellSort2(v);
	
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}
/*
希尔排序时间复杂度非常难以分析，它的平均复杂度界于 O(n) 到 O(n^2) 之间，普遍认为它最好的时间复杂度为 O(n1.3)O(n^{1.3})O(n1.3)。

希尔排序的空间复杂度为 O(1)，只需要常数级的临时变量。
*/